package com.wxweven.algorithm.list;

/**
 * @author wxweven
 */
public class LC160两个链表的相交结点 {

    /**
     * 编写一个程序，找到两个单链表相交的起始节点。
     */

    // 普通解法
    public ListNode v1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        int la = len(headA);
        int lb = len(headB);

        if (la > lb) {
            for (int i = 0; i < la - lb; i++) {
                headA = headA.next;
            }
        } else if (lb > la) {
            for (int i = 0; i < lb - la; i++) {
                headB = headB.next;
            }
        }

        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }

            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }

    public int len(ListNode head) {
        int count = 0;
        while (head != null) {
            head = head.next;
            count++;
        }

        return count;
    }

    // 这个解法很妙
    public ListNode v2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode hA = headA, hB = headB;
        while (hA != hB) {
            hA = hA != null ? hA.next : headB;
            hB = hB != null ? hB.next : headA;
        }
        return hA;
    }
}